\section{Two-hop walk in directed graphs}
\label{sec:directed-10p}
In this section, we analyze the two-hop walk process in directed
graphs.  We say that the process terminates at time $t$ if for every
node $u$ and every node $v$, $\gf{t}$ contains the edge $(u,v)$
whenever $u$ has a path to $v$ in $\gf{0}$.

\begin{theorem}
\label{thm:directed.upper-10p}
On any $n$-node directed graph, the two-hop walk terminates in
$O(n^2 \log n)$ rounds with high probability.  Furthermore, there
exists a (weakly connected) directed graph for which the process takes
$\Omega(n^2 \log n)$ rounds to terminate.
\end{theorem}
\begin{proof}
Consider any pair of nodes, $u$ and $v$.  Consider a shortest path
from $u$ to $v$ $\rb{v_0,v_1,v_2,\dots,v_m}$, where $v_0 = u$, $v_m =
v$ and $m \le n$.  Fix a time step $t$.  Let $e_i$ denote the event an
edge is added from $v_i$ to $v_{i+2}$ in step $t$. The probability of
occurrence of $e_i$ is $\prob{e_i}\ge 1/n^2$. All the $e_i$'s are
independent from one another.
\begin{eqnarray*}
\prob{\cup_i e_i} &\ge& \sum_i \prob{e_i} - \sum_i \sum_j \prob{e_i\cap e_j} \\
 &=& \sum_i \prob{e_i} - \sum_i \sum_j \prob{e_i} \prob{e_j} \\
 &\ge& m\frac{1}{n^2} - m(m-1) \frac{1}{n^4} \\
 &\ge& \frac{m}{n^2}
\end{eqnarray*}
Let $X_1$ denote the number of steps it takes for the length of the
above path to decrease by $1$.  It is clear that $E[X_1] \le n^2/m$.
In general, let $X_i$ denote the number of steps it takes for the
length of the above path to decrease by $i$.  By
Lemma~\ref{lem:couponcorollary-10p}, the number of steps it takes for
the above path to shrink to an edge is at most $4 n^2 \ln n$ with
probability $1/n^3$.  Taking a union bound over all the edges yields
the desired upper bound.

For the lower bound, consider a graph $\gf{0}$ with the node set
$\{1, 2, \ldots, n\}$ and the edge set 
\[
\{(3i,j), (3i+1,j): 0 \le i < n/4, 3n/4 \le j < n \} \bigcup \{(3i,
3i+1), (3i+1, 3i+2): 0 \le i < n/4\}.
\] 
The only edges that need to be added by the two-hop process are the
edges $(3i,3i+2)$ for $0 \le i < n/4$.  The probability that node
$3i$ adds the edge $(3i,3i+2)$ in any round is at most $16/n^2$.  The
probability that edge $(3i,3i+2)$ is not added in $(n^2 \ln n)/32$
rounds is at least $1/\sqrt{n}$.  Since the events associated with
adding each of these edges are independent, the probability that all
the $n/3$ edges are added in $(n^2 \ln n)/32$ rounds is at most $(1 -
1/\sqrt{n})^{n/3} \le e^{-\sqrt{n}/3}$, completing the lower bound
proof.
\end{proof}

The lower bound in the above theorem takes advantage of the fact that the
initial graph is not strongly connected.  Extending the above analysis
for strongly connected graphs appears to be much more difficult since
the events corresponding to the addition of new edges interact in
significant ways.  We present an $\Omega(n^2)$ lower bound for a
strongly connected graph by a careful analysis that tracks the event
probabilities with time and takes dependencies into account.  The
graph $\gf{0}$, depicted in Figure~\ref{fig:digraph+lower}, is
similar to the example in~\cite{leighton} used to establish an
$\Omega(n)$ lower bound on the Random Pointer Jump algorithm, in which
each node gets to know all the neighbors of a random neighbor in each
step.  Since the graphs are constantly changing over time in both the
processes, the dynamic edge distributions differ significantly in the
two cases, and we need a substantially different analysis. 

\begin{theorem}
\label{thm:directed.lower-10p}
There exists a strongly connected directed graph for which
the expected number of rounds taken by the two-hop process is
$\Omega(n^{2})$.
\end{theorem}
\begin{proof}
The graph $\gf{0}=(V,E)$ is depicted in Figure~\ref{fig:digraph+lower}
and formally defined as $\gf{0} = (V,E)$ where $V=\cub{1,2,\dots,n}$
with $n$ being even, and
\[
E = \cub{\rb{i,j}: 1 \le i,j \le n/2} \cup \cub{\rb{i,i+1} : n/2 \le i <
  n} \cup \cub{\rb{i,j}: i > j, i > n/2, i,j\in V}.
\]
\begin{figure}[ht]
\begin{center}
  \includegraphics[width=5in]{./figures/diexample.jpg}
  \caption{Lower bound example for two-hop walk process in directed graphs}
  \label{fig:digraph+lower}
\end{center}
\end{figure}
We first establish an upper bound on the probability that edge
$(i,i+h)$ is added by the start of round $t$, for given $i$, $1 \le i
\le n -h$.  Let $\prb{h}{t}$ denote this probability.  The following
base cases are immediate: $\prb{h}{0}$ is $1$ for $h = 1$ and $h < 0$,
and $0$ otherwise.  Next, the edge $(i,i+h)$ is in $\gf{t+1}$ if and
only if $(i,i+h)$ is either in $\gf{t-1}$ or added in round $t$.  In
the latter case, $(i,i+h)$ is added by a two-hop walk $i \rightarrow i
+ k \rightarrow i + h$, where $-i < k \le n - i$.  Since the
out-degree of every node is at least $n/2$, for any $k$ the
probability that $i$ takes such a walk is at most $4/n^2$.
\begin{eqnarray}
\prb{h}{t+1} & \le & \prb{h}{t} + \frac{4}{n^2} \sum_{k > -i}^{n-i} \prb{k}{t}\prb{h-k}{t} \nonumber\\
& = & \prb{h}{t} + \frac{4}{n^2} \left(\sum_{k = 1}^{i-1} \prb{h+k}{t} + \sum_{k=1}^{h-1} \prb{k}{t}\prb{h-k}{t} + \sum_{k=h+1}^{n-i} \prb{k}{t}\right) \label{eqn:lower}
\end{eqnarray}
We show by induction on $t$ that 
\begin{eqnarray}
\prb{h}{t} \le \left(\frac{\alpha t}{n^2}\right)^{h-1}, \mbox{ for all } t \le \eps n^2  \label{eqn:prb}
\end{eqnarray}
where $\alpha$ and $\eps$ are positive constants that are specified
later.

The induction base is immediate.  For the induction step, we use the
induction hypothesis for $t$ and Equation~\ref{eqn:lower} and bound
$\prb{h}{t+1}$ as follows.
\begin{eqnarray*}
\prb{h}{t+1} & \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + \frac{4}{n^2} \left(\sum_{k = 1}^{i-1} \left(\frac{\alpha t}{n^2}\right)^{h+k-1} + \sum_{k=1}^{h-1} \left(\frac{\alpha t}{n^2}\right)^{k-1} \left(\frac{\alpha t}{n^2}\right)^{h-k-1} + \sum_{k=h+1}^{n-i} \left(\frac{\alpha t}{n^2}\right)^{k-1}\right)\\
& \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + \frac{4}{n^2} \left( (h-1)\left(\frac{\alpha t}{n^2}\right)^{h-2} + \left(\frac{\alpha t}{n^2}\right)^{h} \frac{2}{1 - \alpha t/n^2}\right)\\
& \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + (h-1)\left(\frac{\alpha t}{n^2}\right)^{h-2}\frac{1}{n^2} \left(4 + \frac{4\eps^2}{(1 - \alpha\eps)}\right)\\
& \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + (h-1) \left(\frac{\alpha t}{n^2}\right)^{h-2}\frac{\alpha}{n^2}\\
& \le & \left(\frac{\alpha (t+1)}{n^2}\right)^{h-1}.
\end{eqnarray*}
(In the second inequality, we combine the first and third summations
and bound them by their infinite sums.  In the third inequality, we
use $t \le \eps n^2$.  For the fourth inequality, we set $\alpha$
sufficiently large so that $\alpha \ge 4 + 4/(1-\alpha \eps)$.  The
final inequality follows from Taylor series expansion.)

For an integer $x$, let $C_x$ denote the cut $(\{u: u \le x\}, \{v, v
> x\})$.  We say that a cut $C_x$ is {\em untouched}\/ at the start of
round $t$ if the only edge in $\gf{t}$ crossing the cut $C_x$ is the
edge $(x, x+1)$; otherwise, we say $C_x$ is {\em touched}.  Let $X$
denote the smallest integer such that $C_X$ is untouched.  We note
that $X$ is a random variable that also varies with time.  Initially,
$X = n/2$.

We divide the analysis into several phases, numbered from $0$.  A
phase ends when $X$ changes.  Let $X_i$ denote the value of $X$ at the
start of phase $i$; thus $X_0 = n/2$.  Let $T_i$ denote the number of
rounds in phase $i$.  A new edge is added to the cut $C_{X_i}$ only if
either $X_i$ selects edge $(X_i,X_i+1)$ as its first hop or a node
$u < X_i$ selects $u \rightarrow X_i \rightarrow X_i + 1$.  Since the
degree of every node is at least $n/2$, the probability that a new
edge is added to the cut $C_i$ is at most $2/n + n(4/n^2) = 6/n$,
implying that $E[T_i] \ge n/6$.

We now place a bound on $X_{i+1}$.  Fix a round $t \le \eps n^2$, and
let $E_x$ denote the event that $C_x$ is touched by round $t$.  We
first place an upper bound on the probability of $E_x$ for arbitrary
$x$ using Equation~\ref{eqn:prb}.
\[
\Pr[E_x] \le \sum_{h \ge 2} h \left(\frac{\alpha t}{n^2} \right)^{h-1} \le \frac{\alpha t (4 - 3(\alpha t)/n^2 + (\alpha t)^2/n^4)}{n^2(1-(\alpha t)/n^2)^3},
\]
for $t \le \eps n^2$, where we use the inequality $\sum_{h \ge 2} h^2
\delta^h = \delta(4-3\delta+\delta^2)/(1-\delta)^3$ for $0 < \delta <
1$.  We set $\eps$ sufficiently small so that
$(4-3\eps+\eps^2)/(1-\eps)^3 \le 5$, implying that the above
probability is at most $5\eps$.

If $E_x$ were independent from $E_y$ for $x \neq y$, then we can
invoke a straightforward analysis using a geometric probability
distribution to argue that $E[X_{i+1} - X_i]$ is at most $1/(1-5\eps)
= O(1)$; to see this, observe that $X_{i+1} - X_i$ is stochastically
dominated by the number of tosses of a biased coin needed to get one
head, where the probability of tail is $5\eps$.  The preceding
independence does not hold, however; in fact, for $y > x$, $\Pr[E_y
  \mod E_x] > \Pr[E_y]$.  We show that the impact of this correlation
is very small when $x$ and $y$ are sufficiently far apart.  We
consider a sequence of cuts $C_{x_1}, C_{x_2}, \ldots, C_{x_\ell},
\ldots$ where $x_\ell = x_{\ell-1} + c\ell$, for a constant $c$ chosen
sufficiently large, and we set $x_0 = X_i + 2$.  We bound the
conditional probability of $E_{x_\ell}$ given $E_{x_{\ell -1}} \cap
E_{x_{\ell-2}} \cdots \cap E_{x_1}$ as follows.
\begin{eqnarray*}
& & \Pr[E_{x_\ell} | E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]\\
& = & \frac{\Pr[E_{x_\ell} \cap E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]}{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]}\\
& \le & \frac{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1} \cap (C_{x_\ell} \cap (C_{x_{\ell-1}} \cup \cdots \cup C_{x_1}) = \emptyset)]}{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]} +\\
& & 
\frac{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1} \cap (C_{x_\ell} \cap (C_{x_{\ell-1}} \cup \cdots \cup C_{x_1}) \neq \emptyset)}{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]}\\
& \le & \frac{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}] \Pr[\mbox{a new edge is added from } (x_{\ell-1} +1, x_\ell) \mbox{ to } (x_\ell+1,n]]}{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]}\\
& & \frac{\Pr[\mbox{an edge spanning at least } c\ell \mbox{ hops is added across } C_{x_\ell}]}{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]}\\
& \le & \Pr[E_{x_\ell}] + \frac{((\alpha t)/n^2)^{c\ell-1}}{(1 - \alpha t/n^2)^2(t/n^2)^{\ell}}\\
& \le & 5\eps + \eps = 6\eps,
\end{eqnarray*}
where we set $c$ sufficiently large in the last step.  Since $X_{i+1}$
is at most the smallest $x_\ell$ such that $C_{x_\ell}$ is untouched, 
we obtain that
\begin{eqnarray*}
E[X_{i+1} - X_i] \le 2 + \sum_{\ell \ge 2} (6 \eps)^\ell c\ell^2 \le c',
\end{eqnarray*}
for a constant $c'$ chosen sufficiently large.  We thus obtain that
after $\eps' n$ phases, $E[X]$ is at most $\eps'c' n$, where $\eps'$
is chosen sufficiently small so that $n - E[X]$ is $\Omega(n)$.  Since
the expected length of each phase is at least $n/6$, it follows that
the expected number of rounds it takes for the two-hop process to
complete is $\Omega(n^2)$ rounds.  \junk{Let $e_i$ be the event of
  adding an edge from node $i$ to node $i+2$. $\prob{e_i}\le 4/n^2$
  $\forall i\ge n/2$. And all $e_i$'s are independent. We will show it
  takes $\Omega(n^{2})$ time for all $e_i$'s ($i\ge n/2$) to
  happen. Let $r_i$ be the event of adding an edge from node $i$ to
  node $i+3$. $\forall i$, the probability that $r_i$ happens in
  $n^{2}/4$ rounds is
\begin{eqnarray*}
\prob{r_i\mbox{ in }n^{2}/4\mbox{ rounds}} &=& {n^{2}/4 \choose 2}\prob{e_i}\prob{r_i|e_i} \\
&=& \frac{n^2/4(n^2/4-1)}{2} \frac{4}{n^2} \frac{4}{n^2} \\
&\le& \frac{1}{2}
\end{eqnarray*}
Therefore,
\[\prob{\mbox{more than }\ln n\mbox{ } r_i\mbox{'s happen in }n^2/4\mbox{ rounds}} \le \frac{1}{n}\]
\begin{figure}[ht]
\begin{center}
  \includegraphics[width=3in]{./figures/diexample2.jpg}
  \caption{Bad events of 2-step random walk in directed graph}
  \label{fig:digraph+lower+badevent}
\end{center}
\end{figure}
As shown in Figure \ref{fig:digraph+lower+badevent}, such $r_v$ event
will increase the probability of $e_{v+1}$. Since such bad event won't
be more than $\ln n$ with probability at least $1-1/n$, we can look at
the other $n/2-\ln n$ $e_i$'s. In $n^2/4$ rounds, with constant
probability not all $e_i$'s will complete. Thus, the lower bound for
2-hop random walk process in directed graph is $\Omega(n^2)$.
}

\end{proof}


\junk{

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=5in]{./figures/diexample.jpg}
  \caption{Lower bound example for two-hop walk process in directed graphs}
  \label{fig:digraph+lower}
\end{center}
\end{figure}

\begin{proofsketch}
The graph $\gf{0}=(V,E)$ is depicted in Figure~\ref{fig:digraph+lower}
and formally defined as $\gf{0} = (V,E)$ where $V=\cub{1,2,\dots,n}$
with $n$ being even, and
\[
E = \cub{\rb{i,j}: 1 \le i,j \le n/2} \cup \cub{\rb{i,i+1} : n/2 \le i <
  n} \cup \cub{\rb{i,j}: i > j, i > n/2, i,j\in V}.
\]
We first establish an upper bound on the probability that edge
$(i,i+h)$ is added by the start of round $t$, for given $i$, $1 \le i
\le n -h$.  Let $\prb{h}{t}$ denote this probability.  The following
base cases are immediate: $\prb{h}{0}$ is $1$ for $h = 1$ and $h < 0$,
and $0$ otherwise.  Next, the edge $(i,i+h)$ is in $\gf{t+1}$ if and
only if $(i,i+h)$ is either in $\gf{t-1}$ or added in round $t$.  In
the latter case, $(i,i+h)$ is added by a two-hop walk $i \rightarrow i
+ k \rightarrow i + h$, where $-i < k \le n - i$.  Since the
out-degree of every node is at least $n/2$, for any $k$ the
probability that $i$ takes such a walk is at most $4/n^2$.
\begin{eqnarray}
\prb{h}{t+1} & \le & \prb{h}{t} + \frac{4}{n^2} \sum_{k > -i}^{n-i} \prb{k}{t}\prb{h-k}{t} = \prb{h}{t} + \frac{4}{n^2} \left(\sum_{k = 1}^{i-1} \prb{h+k}{t} + \sum_{k=1}^{h-1} \prb{k}{t}\prb{h-k}{t} + \sum_{k=h+1}^{n-i} \prb{k}{t}\right) \label{eqn:lower-10p}
\end{eqnarray}
In Appendix~\ref{app:directed}, we show by induction on $t$ that
\begin{eqnarray}
\prb{h}{t} \le \left(\frac{\alpha t}{n^2}\right)^{h-1}, \mbox{ for all } t \le \eps n^2  \label{eqn:prb-10p}
\end{eqnarray}
where $\alpha$ and $\eps$ are positive constants that are specified
later.
\junk{
The induction base is immediate.  For the induction step, we use the
induction hypothesis for $t$ and Equation~\ref{eqn:lower-10p} and bound
$\prb{h}{t+1}$ as follows.
\begin{eqnarray*}
\prb{h}{t+1} & \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + \frac{4}{n^2} \left(\sum_{k = 1}^{i-1} \left(\frac{\alpha t}{n^2}\right)^{h+k-1} + \sum_{k=1}^{h-1} \left(\frac{\alpha t}{n^2}\right)^{k-1} \left(\frac{\alpha t}{n^2}\right)^{h-k-1} + \sum_{k=h+1}^{n-i} \left(\frac{\alpha t}{n^2}\right)^{k-1}\right)\\
& \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + \frac{4}{n^2} \left( (h-1)\left(\frac{\alpha t}{n^2}\right)^{h-2} + \left(\frac{\alpha t}{n^2}\right)^{h} \frac{2}{1 - \alpha t/n^2}\right)\\
& \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + (h-1)\left(\frac{\alpha t}{n^2}\right)^{h-2}\frac{1}{n^2} \left(4 + \frac{4\eps^2}{(1 - \alpha\eps)}\right)\\
& \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + (h-1) \left(\frac{\alpha t}{n^2}\right)^{h-2}\frac{\alpha}{n^2}\\
& \le & \left(\frac{\alpha (t+1)}{n^2}\right)^{h-1}.
\end{eqnarray*}
(In the second inequality, we combine the first and third summations
and bound them by their infinite sums.  In the third inequality, we
use $t \le \eps n^2$.  For the fourth inequality, we set $\alpha$
sufficiently large so that $\alpha \ge 4 + 4/(1-\alpha \eps)$.  The
final inequality follows from Taylor series expansion.)
}

For an integer $x$, let $C_x$ denote the cut $(\{u: u \le x\}, \{v, v
> x\})$.  We say that a cut $C_x$ is {\em untouched}\/ at the start of
round $t$ if the only edge in $\gf{t}$ crossing the cut $C_x$ is the
edge $(x, x+1)$; otherwise, we say $C_x$ is {\em touched}.  Let $X$
denote the smallest integer such that $C_X$ is untouched.  We note
that $X$ is a random variable that also varies with time.  Initially,
$X = n/2$.

We divide the analysis into several phases, numbered from $0$.  A
phase ends when $X$ changes.  Let $X_i$ denote the value of $X$ at the
start of phase $i$; thus $X_0 = n/2$.  Let $T_i$ denote the number of
rounds in phase $i$.  A new edge is added to the cut $C_{X_i}$ only if
either $X_i$ selects edge $(X_i,X_i+1)$ as its first hop or a node $u
< X_i$ selects $u \rightarrow X_i \rightarrow X_i + 1$.  Since the
degree of every node is at least $n/2$, the probability that a new
edge is added to the cut $C_i$ is at most $2/n + n(4/n^2) = 6/n$,
implying that $E[T_i] \ge n/6$.

We now place a bound on $X_{i+1}$.  Fix a round $t \le \eps n^2$, and
let $E_x$ denote the event that $C_x$ is touched by round $t$.  We
first place an upper bound on the probability of $E_x$ for arbitrary
$x$ using Equation~\ref{eqn:prb-10p}.
\[
\Pr[E_x] \le \sum_{h \ge 2} h \left(\frac{\alpha t}{n^2} \right)^{h-1} \le \frac{\alpha t (4 - 3(\alpha t)/n^2 + (\alpha t)^2/n^4)}{n^2(1-(\alpha t)/n^2)^3},
\]
for $t \le \eps n^2$, where we use the inequality $\sum_{h \ge 2} h^2
\delta^h = \delta(4-3\delta+\delta^2)/(1-\delta)^3$ for $0 < \delta <
1$.  We set $\eps$ sufficiently small so that
$(4-3\eps+\eps^2)/(1-\eps)^3 \le 5$, implying that the above
probability is at most $5\eps$.

If $E_x$ were independent from $E_y$ for $x \neq y$, then we can
invoke a straightforward analysis using a geometric probability
distribution to argue that $E[X_{i+1} - X_i]$ is at most $1/(1-5\eps)
= O(1)$; to see this, observe that $X_{i+1} - X_i$ is stochastically
dominated by the number of tosses of a biased coin needed to get one
head, where the probability of tail is $5\eps$.  The preceding
independence does not hold, however; in fact, for $y > x$, $\Pr[E_y
  \mod E_x] > \Pr[E_y]$.  We show that the impact of this correlation
is very small when $x$ and $y$ are sufficiently far apart.  We
consider a sequence of cuts $C_{x_1}, C_{x_2}, \ldots, C_{x_\ell},
\ldots$ where $x_\ell = x_{\ell-1} + c\ell$, for a constant $c$ chosen
sufficiently large, and we set $x_0 = X_i + 2$.  In
Appendix~\ref{app:directed}, we bound the conditional probability of
$E_{x_\ell}$ given $E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots \cap
E_{x_1}$ to be at most $6\eps$, by setting $\eps$ and $c$
appropriately.  Since $X_{i+1}$ is at most the smallest $x_\ell$ such
that $C_{x_\ell}$ is untouched, we obtain that
\begin{eqnarray*}
E[X_{i+1} - X_i] \le 2 + \sum_{\ell \ge 2} (6 \eps)^\ell c\ell^2 \le c',
\end{eqnarray*}
for a constant $c'$ chosen sufficiently large.  We thus obtain that
after $\eps' n$ phases, $E[X]$ is at most $\eps'c' n$, where $\eps'$
is chosen sufficiently small so that $n - E[X]$ is $\Omega(n)$.  Since
the expected length of each phase is at least $n/6$, it follows that
the expected number of rounds it takes for the two-hop process to
complete is $\Omega(n^2)$.
\end{proofsketch}
}
